| 翻訳と辞書 |
| Černý conjecture ： ウィキペディア英語版 |
Synchronizing word
In computer science, more precisely, in the theory of deterministic finite automata (DFA), a synchronizing word or reset sequence is a word in the input alphabet of the DFA which sends any state of the DFA to one and the same state.〔Avraham Trakhtman: (''Synchronizing automata, algorithms, Cerny Conjecture'' ). Accessed May 15, 2010.〕 That is, if an ensemble of copies of the DFA are each started in different states, and all of the copies process the synchronizing word at the same speed, they will all end up reaching the same state as each other, at the same time as each other. Not every DFA has a synchronizing word; for instance, a DFA with two states, one for words of even length and one for words of odd length, can never be synchronized.
==Length==
The problem of estimating the length of synchronizing words has a long history and was posed independently by several authors, but it is commonly known as the Černý conjecture. In 1964 Jan Černý conjectured that (''n'' − 1)2 is the upper bound for the length of the shortest synchronizing word for any ''n''-state complete DFA (a DFA with complete state transition graph).〔〔 (in Slovak).〕 If this is true, it would be tight: in his 1964 paper, Černý exhibited a class of automata (indexed by the number ''n'' of states) for which the shortest reset words have this length. The best upper bound known is (''n'' 3 - n)/6, far from the lower bound.〔http://arxiv.org/abs/1104.2409v7 Trahtman at one point thought he had proven a better bound of n(7''n''2+6n−16)/48, but this proof turned out to be incorrect and the paper has been retracted, leaving the best-known bound to be (n^3 - n)/6〕
For ''n''-state DFAs over a ''k''-letter input alphabet, an algorithm by David Eppstein finds a synchronizing word of length at most 11''n''3/48 + O(''n''2), and runs in time complexity O(''n''3+''kn''2). This algorithm does not always find the shortest possible synchronizing word for a given automaton; as Eppstein also shows, the problem of finding the shortest synchronizing word is NP-complete. However, for a special class of automata in which all state transitions preserve the cyclic order of the states, he describes a different algorithm with time O(''kn''2) that always finds the shortest synchronizing word, proves that these automata always have a synchronizing word of length at most (''n'' − 1)2 (the bound given in Černý's conjecture), and exhibits examples of automata with this special form whose shortest synchronizing word has length exactly (''n'' − 1)2.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Synchronizing word」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|